use rand::Rng;

fn rand_int(l: i64, r: i64) -> i64 {
    let mut rng = rand::thread_rng();
    rng.gen_range(l..r)
}


fn quick_power(a: i64, b: i64, p: i64) -> i64 {
    let mut res = 1;
    let mut a = i128::from(a);
    let mut b = b;
    let p = i128::from(p);
    while b > 0 {
        if b & 1 != 0 {
            res = (i128::from(res) * a % p) as i64;
        }
        a = a * a % p;
        b >>= 1;
    }
    res
}

fn miller_rabin(n: i64) -> bool {
    if n < 3 || n % 2 == 0 {
        return n == 2;
    }
    let mut a = n - 1;
    let mut b = 0;
    while a % 2 == 0 {
        a /= 2;
        b += 1;
    }
    for _ in 0..10 {
        let x = rand_int(2, n - 1);
        let mut v = quick_power(x, a, n);
        if v == 1 {
            continue;
        }
        let mut j = 0;
        while j < b {
            if v == n - 1 {
                break;
            }
            v = (i128::from(v) * i128::from(v) % i128::from(n)) as i64;
            j += 1;
        }
        if j == b {
            return false;
        }
    }
    true
}

fn get_next(start: i64, step: i64) -> Vec<i64> {
    vec![start, start + step, start + 2 * step, start + 3 * step]
}

pub fn min_edge_prime_num(number: u32) -> String {
    let mut total = 5;
    let mut num_of_prims = 3;
    let mut start = vec![3, 5, 7, 9];
    let mut step;

    for i in (5..).step_by(2) {
        step = i - 1;
        start = get_next(start[3] + step, step);

        total += 4;
        if miller_rabin(start[0]) {
            num_of_prims += 1;
        }
        if miller_rabin(start[1]) {
            num_of_prims += 1;
        }
        if miller_rabin(start[2]) {
            num_of_prims += 1;
        }
        // if miller_rabin(start[3]) {
        //     num_of_prims += 1;
        // }

        if total * number > num_of_prims * 100 {
            return format!("{},{}", (total + 1) / 2, num_of_prims);
        }
    }
    "".to_string()
}
